package leetcode.l0526;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author Retain
 * @date 2021/5/26 17:38
 */
public class Easy_二叉树的中序遍历_94 {
    ArrayList<Integer> list = new ArrayList<>();

    /**
     * 迭代算法
     * @param root
     * @return
     */
    public List<Integer> inorderTraversalIteration(TreeNode root) {
        if (null != root) {
            Stack<TreeNode> stack = new Stack<>();
            TreeNode currentNode = root;

            while (currentNode != null || !stack.isEmpty()) {
                // 先将左子树全部入栈
                while (currentNode != null) {
                    stack.push(currentNode);
                    currentNode = currentNode.left;
                }
                // 一个一个出栈，出栈的同时进行中序遍历输出
                if (!stack.isEmpty()) {
                    currentNode = stack.pop();
                    // 输出左结点
                    list.add(currentNode.val);
                    // 切换右子树（当前根节点也是左子树的一部分，如果有右子树则打印后进入）
                    currentNode = currentNode.right;
                }
            }
        }
        return list;
    }
    /**
     * 递归算法
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return list;
        }
        if (root.left != null) {
            inorderTraversal(root.left);
        }
        list.add(root.val);
        if (root.right != null) {
            inorderTraversal(root.right);
        }
        return list;
    }

}
